package BinarySearch;

/*
有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xel3tc/
 */

public class _62有效的完全平方数 {
    public static void main(String[] args) {

        System.out.println(Math.sqrt(808201));
        System.out.println(isPerfectSquare2(808201));

    }

    //超时
    //暴力为啥超时   缺失了提前结束循环的条件 并且 没有考虑数值溢出的情况
    //官解的暴力更合理
    //O(n)
    public boolean isPerfectSquare(int num) {
        if(num == 1){
            return true;
        }
        for (int i = 2; i <= num / 2; i++) {
            long square = (long)i * i;
            if(square == num){
                return true;
            }
            if(square > num){
                break;
            }
        }
        return false;
    }

    //官解： 暴力
    class Solution {
        public boolean isPerfectSquare(int num) {
            long x = 1, square = 1;
            while (square <= num) {
                if (square == num) {
                    return true;
                }
                ++x;
                square = x * x;
            }
            return false;
        }
    }

    //二分查找
    //O(log n)  O(1)
    public static boolean isPerfectSquare2(int num) {
        if(num == 1){
            return true;
        }
        int n = num / 2;
        int left = 2,right = n;
        while(left <= right){
            int mid = left + (right - left)/2;
            long midNum =(long)mid * mid;
            if(midNum == num){
                return true;
            }else if(midNum > num){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return false;
    }
}
